
package temp.list

/**
 * 一个简单的单向链表实现，用于存储字符串元素
 */
class LinkedList {
    // 链表的头节点
    private var head: Node = _

    /**
     * 向链表尾部添加一个元素
     * @param element 要添加的字符串元素
     */
    def add(element: String): Unit = {
        val newNode = new Node(element)

        val it = tail(head)
        if (it == null) {
            head = newNode
        } else {
            it.next = newNode
        }
    }

    /**
     * 找到链表的最后一个节点
     * @param head 链表的头节点
     * @return 链表的最后一个节点，如果链表为空则返回null
     */
    private def tail(head: Node) = {
        var it: Node = null

        it = head
        while (it != null && it.next != null) {
            it = it.next
        }

        it
    }

    /**
     * 从链表中移除指定元素
     * @param element 要移除的字符串元素
     * @return 如果成功移除元素返回true，否则返回false
     */
    def remove(element: String): Boolean = {
        var result = false
        var previousIt: Node = null
        var it: Node = head
        while (!result && it != null) {
            if (0 == element.compareTo(it.data)) {
                result = true
                unlink(previousIt, it)
            }
            previousIt = it
            it = it.next
        }

        result
    }

    /**
     * 从链表中解除指定节点的链接
     * @param previousIt 要解除链接的节点的前一个节点
     * @param currentIt 要解除链接的节点
     */
    private def unlink(previousIt: Node, currentIt: Node): Unit = {
        if (currentIt == head) {
            head = currentIt.next
        } else {
            previousIt.next = currentIt.next
        }
    }

    /**
     * 获取链表中元素的数量
     * @return 链表中元素的数量
     */
    def size(): Int = {
        var size = 0

        var it = head
        while (it != null) {
            size = size + 1
            it = it.next
        }

        size
    }

    /**
     * 获取指定索引位置的元素
     * @param idx 要获取元素的索引位置
     * @return 指定索引位置的字符串元素
     * @throws IndexOutOfBoundsException 如果索引超出范围
     */
    def get(idx: Int): String = {
        var index = idx
        var it = head
        while (index > 0 && it != null) {
            it = it.next
            index = index - 1
        }

        if (it == null) {
            throw new IndexOutOfBoundsException("Index is out of range")
        }

        it.data
    }

    /**
     * 链表节点内部类
     * @param data 节点存储的数据
     */
    private class Node(val data: String) {
        // 指向下一个节点的引用
        var next: Node = _
    }
}

